9002. Chocolate lover
Aziz is very fond
of eating chocolate. But since chocolate is very bad for teeth, his father won’t
let him eat a lot of chocolate. This time he managed to convince his father and
get permission to eat one chocolate every day. Aziz loves two types of
chocolate. One weighs a grams,
the other b grams. Aziz’s father
allowed him to eat one chocolate every day for n days, but with condition that he should not eat the same
chocolate for two days in a row. Now Aziz is worried about only one question.
How to make sure that within n days he could eat the maximum amount (in
grams) of chocolate.
Help him with
this.
Input. One line contains three integers n, a and b (1 ≤ n, a, b ≤ 109)
.
Output. Print the maximum amount of chocolate (in
grams) that Aziz can consume during n
days.
|
Sample
input 1 |
Sample
output 1 |
|
1 10 8 |
10 |
|
|
|
|
Sample
input 2 |
Sample
output 2 |
|
3 1 2 |
5 |
SOLUTION
greedy
Algorithm analysis
If the number of days n is even, Aziz can eat chocolate either in the order a b a b … a b, or in the order b a b … a b a. However, in both cases,
he will consume (a + b) * n
/ 2 grams of chocolate.
If n
is odd, Aziz can consume chocolate in one of the following orders: a b a b … a, or b a b … a b. In the first case, he will consume n / 2 * b + (n + 1) / 2 * a
grams of chocolate, in the second case n / 2 * a + (n + 1) / 2 * b grams. Now we
need to determine in which of these options the amount of chocolate is greater.
Indeed, the sequence a b a b … a of length n (n is odd) contains 
letters a and 
letters b.
Algorithm realization
Read the input data.
scanf("%lld %lld %lld",
&n, &a, &b);
Find the
answer if the number of days n is even.
if (n % 2 == 0)
res =
n / 2 * (a + b);
else
Find the
answer if the number of days n is odd.
{
x = n
/ 2 * a + ((n + 1) / 2 * b);
y = n
/ 2 * b + ((n + 1) / 2 * a);
res =
(x > y) ? x : y;
}
Print the answer.
printf("%lld\n",
res);
Java realization
import java.util.*;
class Main
{
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
Read the input data.
long n = con.nextLong();
long a = con.nextLong();
long b = con.nextLong();
long res = 0;
Find the
answer if the number of days n is even.
if (n % 2 ==
0)
res = n / 2 *
(a + b);
Find the
answer if the number of days n is odd.
else
{
long x = n / 2 * a + ((n + 1) /
2 * b);
long y = n / 2 * b + ((n + 1) /
2 * a);
res = (x > y) ? x : y;
}
Print the answer.
System.out.println(res);
con.close();
}
}
Python realization
Read the input data.
n, a, b = map(int, input().split())
res = 0
Find the
answer if the number of days n is even.
if n % 2 == 0:
res = n // 2 * (a + b)
Find the
answer if the number of days n is odd.
else:
x = n // 2 * a + ((n + 1) // 2 * b)
y = n // 2 * b + ((n + 1) // 2 * a)
if x > y:
res = x
else:
res = y
Print the answer.
print(res)